package org.example.Greedy_Algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class Give_out_candy {
    public static void main(String[] args) {
        //分发糖果

        //n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
        //你需要按照以下要求，给这些孩子分发糖果：
        //每个孩子至少分配到 1 个糖果。
        //相邻两个孩子评分更高的孩子会获得更多的糖果。
        //请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
        int[] ratings = {1, 2, 87, 87, 87, 2, 1};
        int candy = candy(ratings);
        System.out.println(candy);
    }

    public static int candy(int[] ratings) {
        if (ratings.length == 1) return 1;
        int[] arr = Arrays.copyOf(ratings, ratings.length);
        Arrays.sort(arr);
        int[] score = new int[ratings.length];
        Arrays.fill(score, 1);
        for (int i = 0; i < arr.length; i++) {
            if (i != 0 && arr[i] == arr[i - 1]) continue;
            for (int j = 0; j < ratings.length; j++) {
                if (arr[i] == ratings[j]) {
                    if (j > 0 && j < ratings.length - 1) {
                        if (ratings[j - 1] > ratings[j] && score[j - 1] <= score[j]) {
                            score[j - 1] = score[j] + 1;
                        }
                        if (ratings[j + 1] > ratings[j] && score[j + 1] <= score[j]) {
                            score[j + 1] = score[j] + 1;
                        }
                    } else if (j == 0) {
                        if (ratings[j + 1] > ratings[j] && score[j + 1] <= score[j]) {
                            score[j + 1] = score[j] + 1;
                        }
                    } else if (j == ratings.length - 1) {
                        if (ratings[j - 1] > ratings[j] && score[j - 1] <= score[j]) {
                            score[j - 1] = score[j] + 1;
                        }
                    }
                }
            }
        }
        System.out.println(Arrays.toString(score));
        int num = 0;
        for (int i : score) {
            num+=i;
        }
        return num;
    }
}
